In computer technology, data transmission and control technology, the representation of information in the binary system of numbers has gained wide acceptance. Numbers in the binary system are expressed by two digits only, viz. 0 (zero) and 1 (unity). The use of the binary system is a convenient expedient, because simple bistable systems may be used for the physical representation of data.
Binary representation of information (e.g. data, letters, symbols, etc.) produces sequences consisting only of zeroes and ones. Let this sequence be called an elementary signal sequence or more briefly, a signal sequence.
Among these signal sequences, in the majority of cases the zeroes and ones, i.e. the elementary signals, follow one another in a random order. However, in some actual sequences the elementary signals do not occur at a uniform frequency. Often there are considerable differences in the frequencies of occurrence of the elementary signals. In other sequences, it can be shown that differences will appear in the probability of occurrence of certain shorter or longer sequences of the elementary signals, sequences which may be called letter or blocks, i.e., frequency of the blocks rather than of the elementary signals.
In the course of research in the theory of encoding several procedures have been developed, by means of which the length of elementary signal sequences of information may be reduced, provided that the frequencies of occurrence of elementary signals or of sequences differ from one another. In this manner, for example, the length of a signal sequence of information may successfully be shortened or shrunk by means of codes of varying word lengths.
For the explanation of the use of such codes of variable word lengths let us write down the following elementary signal sequence: . . . 000000000110001000000000000 . . .
Of the 27 elementary signals of the sequence, 24 are zeroes and 3 are ones. Let us form a new elementary signal sequence in conformity with the following rule: Starting at the beginning of the sequence, for each pair of zeroes substitute a single zero, for each one a pair comprising a one and a zero, and for a pair comprising a zero and a one, a pair comprising two ones in order to form a new sequence, i.e. the following rule is applied:
______________________________________ 00 .fwdarw. 1 .fwdarw. 10 (a) 01 .fwdarw. 11 ______________________________________
Bloch was the first to publish this rule of code transformation. On completing the operation, the sequence . . . 00001110011000000 . . . is obtained.
This sequence is about 63 percent. shorter than the original sequence. When the same process is now applied to the new sequence, this will boil down to . . . 0010101001010000 . . . and, if repeated, to . . . 01011110101100 . . .
Hence the sequence originally consisting of 27 signals can be reduced to a sequence of only 14 signals. However, at this point it is no longer worthwhile to continue the procedure, since with an additional step a binary number of 17 digits would be obtained, viz.: . . . 11111010101111100 . . .
The reduction of the length of information signal sequences is a useful procedure, as considerable savings can result from both the transmission and storage of the shorter signal sequences. As a matter of fact, shorter sequences result in information being transmitted at a higher speed. For a given storage capacity, the devices may store more information.
By resorting to an inverse transformation, the shrunk or reduced signal sequences can be decoded to recover the original sequences. For this operation the following transformations are applied:
______________________________________ 11 .fwdarw. 01 10 .fwdarw.1 (b) 0 .fwdarw. 00 ______________________________________
For the shrinkage and restoration, an encoder and a decoder are required the function of which is to transform the signal sequences in conformity with rules (a) and (b). If these operations are to be repeated, as in the example above, provision will have to be made for several encoders and decoders, as well as for intermediate matching units.
The encoders K.sub.1 . . . K.sub.N, in the arrangement in FIG. 1 and the decoders, D.sub.1, D.sub.2, . . . D.sub.N in FIG. 2 carry out the instructions (a) and (b) respectively. However, there is considerable difference in the operating speeds of the various circuits. In FIG. 1 the input of the first encoder K.sub.1 has been given the symbol x.sub.o, while its output is designated x.sub.1. If a signal sequence of a constant frequency f.sub.o is applied to the input x.sub.o, then at the output x.sub.1 the average value of the frequency, f.sub.1, may fluctuate between 0.5 f.sub.o and 2 f.sub.o according to the ratio of zeroes to ones in the input signals. Consequently a signal of fluctuating frequency passes to the input of the encoder K.sub.2, so that the frequency of the signal appearing at point x.sub.2 can change or can even be greater compared to that at x.sub.1. The situation is very much the same with the signal frequencies of the inputs y.sub.o, y.sub.1, . . . y.sub.N in FIG. 2. For the control of the encoding and decoding procedures control circuits V.sub.K and V.sub.D are required, which are, respectively, connected to the circuits K.sub.i and D.sub.i i=1, 2, . . . N. In general the individual encoders and decoders, and therefore the control circuits V.sub.K and V.sub.D, differ from one another. However, the use of a variety of types equipment is fraught with disadvantages.